package org.example.leetcode;
import java.util.*;
/**
 * @version 1.0.0
 * @author: lynn
 * @description: 不含重复数字的数组 nums ，返回其 所有可能的全排列
 * @date: 2021/7/26 14:05
 */
public class LC46 {
    public static void main(String[] args) {
        LC46 lc=new LC46();
        int[] nums={1,2,3};
        System.out.println(lc.permute(nums));
    }

    //fixme 金典回溯算法 https://www.bilibili.com/video/BV1xg4y1v7HR?from=search&seid=11264834503303159928
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();
        if(nums==null || nums.length==0){
            return res;
        }
        backtrack(nums,new ArrayList<Integer>(),res);
        return res;
    }
    private void backtrack(int[] nums,ArrayList<Integer> list,List<List<Integer>> res){
        if (list.size()==nums.length){
            res.add(new ArrayList<>(list)); //fixme java中对象都是应用，我们这个相当于克隆一份
            return;
        }
        for (int i = 0; i <nums.length ; i++) {
            if (list.contains(nums[i])) continue;
            list.add(nums[i]);
            backtrack(nums,list,res);
            list.remove(list.size()-1);
        }
    }
}
